﻿namespace Algorithm.LeetCode
{
    /// <summary>
    /// 第六十九题：x的平方根
    /// </summary>
    public class No69
    {
        /*
         * 实现 int sqrt(int x) 函数。
         * 
         * 计算并返回 x 的平方根，其中 x 是非负整数。
         * 
         * 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
         */

        public static int MySqrt(int x)
        {
            //牛顿迭代法:https://www.cnblogs.com/qlky/p/7735145.html
            //Math.Sqrt(x);
            if (x <= 1)
            {
                return x;
            }
            double last = 0;
            double temp = 1;
            while (temp != last)
            {
                last = temp;
                temp = (temp + x / temp) / 2;
            }
            return (int)temp;
        }
    }
}
